1. Field of the Invention
The present invention relates to an arithmetic coding apparatus and image processing apparatus.
2. Description of the Related Art
An arithmetic coding system that predicts a coding symbol based on states of already coded pixels and carries out arithmetic coding on the prediction result based on a probability estimate of the coding symbol determined for each state is known to have the most excellent characteristic in terms of compressibility.
A QM-coder, a coder adopted by JBIG (ITU Recommendation T.82), is a typical example of an apparatus for carrying out arithmetic coding.
A general configuration and operation of the QM-coder, which is an arithmetic coder for binary images, will be explained below.
As shown in FIG. 18, the QM-coder comprises context generation section 200, context table (context memory) 210, probability estimator 220 and arithmetic coder 230.
Context generation section 200 detects 1024 states created by 10 pixels surrounding to a coding pixel. FIG. 20 shows an example of a template.
“?” in the figure is the coding pixel and the 10 pixels marked “x” are reference pixels. When coding of one pixel is completed, the template is shifted by one rightward as shown with dotted line in FIG. 20 and coding of the next pixel is performed.
Each of 1024 states determined by the values of 10 pixels is called “context” (hereinafter expressed with “S”). A predicted value of a more probable symbol MPS(s) (that is, if MPS of the coding pixel is predicted as “1” by the context s, MPS(s)=1) and a state number of the probability estimator are read from context memory for each context and output to probability estimator 220.
Probability estimator 220 outputs interval width of a less probable symbol Qe(s) to arithmetic coder 230 based on this information. Here, “Qe” is a probability that LPS will occur and the present specification sometimes refers to Qe as a “symbol occurrence probability” or simply as a “probability estimate”.
Furthermore, interval width of a less probable symbol Qe(s) means the width corresponding to the probability of occurrence of LPS which is calculated by multiplying the probability of occurrence of LPS by the width of an augend. The augend refers to the overall width of a number line shown in FIG. 19.
Arithmetic coder 230 performs arithmetic coding calculations based on the coding symbol, predicted value of MPS(S), and interval width Qs(s), and outputs code stream.
As shown in FIG. 19, arithmetic coding divides a number line of initial value 0 to 1 into two sub-intervals of a more probable symbol (MPS) and a less probable symbol (LPS). A series of coding symbols is associated with a point (a coding point) somewhere within each sub-interval. For the simplicity, the QM-coder uses the convention that the coding point is located at the bottom of the sub-interval.
When a coding symbol matches a predicted value, an MPS width is selected for coding of the symbol and an LPS width is selected otherwise.
As described above, a coding point is provided in this sub-interval and a binary fraction of the point denotes an arithmetic code stream.
When the interval width falls short of a predetermined value, an arithmetic coding calculation repeats the doubling operation until the interval width exceeds a predetermined value (more specifically ½ of the initial value) to maintain the accuracy of decimal points. This processing is called “renormalization”.
Renormalization is also carried out when LPS is coded. That is, when an LPS width is selected as a result of estimation failure, the LPS width is always smaller than ½ of the initial value and therefore renormalization is performed every time.
When renormalization is performed, the MPS value and state number (ST) in context table 210 in FIG. 18 are updated. The state number is updated when the “next state number” written in probability estimation section 220 is overwritten in context table 210. In FIG. 18, this overwrite is indicated by an arrow RX.
With this update of the context table 210, even if the next context is also the same as the previous context (that is, even if the template in FIG. 20 is shifted by one rightward, the positions of 1 and 0 of the reference pixels are the same as the previous positions), the value of Qe(S) that occurs is different.
In this way, a Qe(S) value suitable for a probability distribution of the information source is selected. That is, the coding parameter Qe(s) is more adapted to the target image.
Here, the coding target is not limited to binary data. Multi-valued data such as continuous tone image can also be coded using the QM-coder. However, it is necessary to use a context model which matches the coding target.
For example, a discrete cosine transform coefficient (DCT coefficient) includes a DC component and AC component. The both components have different natures of signal. Therefore, it is important to construct a context model suited to these natures in improving the coding efficiency.
In the current technology, different contexts are created for the DC component and AC component.
The conventional arithmetic coding processing has the following problems.
(Problem 1)
Originally, arithmetic coding is excellent in compressibility, but since it is necessary to repeat generation of a context, estimation of symbol occurrence probability and arithmetic code calculation symbol by symbol, arithmetic coding has a disadvantage that it requires a long processing time. A reduction of the processing speed is quite a big problem in such a field as a digital copier that requires high image quality and high speed processing.
Furthermore, when arithmetic coding is pipelined, if renormalization occurs at some midpoint, disturbance occurs with the pipeline resulting in an increase of useless wait time. The processing efficiency may reduce in this way. Especially, renormalization occurs with considerable frequency and pipeline disturbance is likely to occur in image patterns whose context has continuity. The same problem may also occur in the case of decoding.
Therefore, even if arithmetic coding is pipelined, the accuracy cannot be said to be high and speeding up of arithmetic coding/decoding is not expected much.
(Problem 2)
It is desirable to carry out high accuracy pipeline processing in the case of not only coding of binary data but also coding or decoding of multi-valued data (e.g., numerical data such as orthogonal transform coefficient, etc. obtained by JPEG compression).
However, high-speed arithmetic coding or decoding of numerical values such as orthogonal transform coefficients involves the following problems.
That is, making pipeline processing effectively requires data necessary for the next pipeline stage to be supplied continuously at a constant rate.
For example, performing high-speed decoding requires context indices to be supplied simultaneously to a plurality of symbols which are likely to be reconstructed. A set of these context indices will be called “context index vector”.
It is actually difficult to supply context data of such a vector format at a constant rate. As described above, an orthogonal transform coefficient includes a DC component and AC component. Since the DC component and AC component have statistically different natures, the current technology provides different contexts for the respective components.
It is difficult to supply different contexts consecutively. Thus, when DC components and AC components are mixed in a plurality of symbols to be coded, it is difficult to supply a context index vector at a constant rate.
Therefore, high-speed arithmetic coding of multi-valued data is more difficult than in the case of binary data.
In view of these situations, it is an object of the present invention to implement ultra-high-speed and high compressibility arithmetic coding or decoding irrespective of binary data or multi-valued data, and coordinate the amount of arithmetic coding per block to a fixed value and simplify the subsequent processing.